{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum GCD-Sum of a Subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #binary-search #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #二分查找 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxGcdSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子数组的最大 GCD-Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>nums</code> 和一个整数 <code>k</code>.</p>\n",
    "\n",
    "<p>数组 <code>a</code> 的 <strong>gcd-sum</strong>&nbsp;计算方法如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>设&nbsp;<code>s</code>&nbsp;为&nbsp;<code>a</code>&nbsp;的所有元素的和。</li>\n",
    "\t<li>设&nbsp;<code>g</code>&nbsp;为&nbsp;<code>a</code>&nbsp;的所有元素的 <strong>最大公约数</strong>。</li>\n",
    "\t<li><code>a</code> 的 gcd-sum&nbsp;等于 <code>s * g</code>.</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <em><code>nums</code> 的至少包含 <code>k</code> 个元素的子数组的 <strong>最大 gcd-sum</strong>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [2,1,4,4,4,2], k = 2\n",
    "<b>输出：</b>48\n",
    "<b>解释：</b>我们选择子数组 [4,4,4]，该数组的 gcd-sum 为 4 * (4 + 4 + 4) = 48。\n",
    "可以证明我们无法选择任何其他 gcd-sum 大于 48 的子数组。</pre>\n",
    "\n",
    "<p><b>示例 2：</b></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [7,3,9,4], k = 1\n",
    "<b>输出：</b>81\n",
    "<b>解释：</b>我们选择子数组 [9]，该数组的 gcd-sum 为 9 * 9 = 81。\n",
    "可以证明我们无法选择任何其他 gcd-sum 大于 81 的子数组。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-gcd-sum-of-a-subarray](https://leetcode.cn/problems/maximum-gcd-sum-of-a-subarray/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-gcd-sum-of-a-subarray](https://leetcode.cn/problems/maximum-gcd-sum-of-a-subarray/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,4,4,4,2]\\n2', '[7,3,9,4]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGcdSum(self, nums: List[int], k: int) -> int:\n",
    "        nlis, res, k = {}, 0, k - 1\n",
    "        for i in nums:\n",
    "            nlis, lis = {}, nlis\n",
    "            if i not in lis: lis[i] = [0,0]\n",
    "            for x, (y,z) in lis.items():\n",
    "                a = gcd(i,x)\n",
    "                if nlis.get(a,[0,0])[0] <= y:\n",
    "                    nlis[a] = [y+1, z+i]\n",
    "                    if y >= k: res = max(res, (z+i)*a)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGcdSum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        ans = max(nums)**2 if k==1 else 0\n",
    "        g1 = {}\n",
    "\n",
    "        for num in nums:\n",
    "            g2 = {num:(num,1)}\n",
    "            for g in g1:\n",
    "                gnew = math.gcd(g,num)\n",
    "                if not (gnew in g2 and g2[gnew][0]>num+g1[g][0]):\n",
    "                        g2[gnew]=(num+g1[g][0],g1[g][1]+1)    \n",
    "                if g2[gnew][1]>=k and g2[gnew][0]*gnew>ans:\n",
    "                    ans = g2[gnew][0]*gnew\n",
    "            g1 = g2\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGcdSum(self, nums: List[int], k: int) -> int:\n",
    "        res, cur = 0, [] # [gcd, sum, len]\n",
    "        for x in nums:\n",
    "            nxt = []\n",
    "            for i in range(len(cur)):\n",
    "                gd, sm, ln = gcd(cur[i][0], x), cur[i][1], cur[i][2]\n",
    "                if nxt and nxt[-1][0] == gd:\n",
    "                    ...\n",
    "                else:\n",
    "                    nxt.append([gd, sm, ln])\n",
    "            if nxt and nxt[-1][0] == x:\n",
    "                ...\n",
    "            else:\n",
    "                nxt.append([x, 0, 0])\n",
    "            for i in range(len(nxt)):\n",
    "                nxt[i][1] += x; nxt[i][2] += 1\n",
    "                \n",
    "\n",
    "            cur = nxt\n",
    "            # print(cur)\n",
    "\n",
    "            for gd, sm, ln in cur:\n",
    "                if ln >= k and res < gd * sm:\n",
    "                    res = gd * sm\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGcdSum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        ans = 0\n",
    "        g1 = {}\n",
    "\n",
    "        for num in nums:\n",
    "            if k==1 and ans<num*num: ans = num*num\n",
    "            g2 = {num:(num,1)}\n",
    "            for g in g1:\n",
    "                gnew = math.gcd(g,num)\n",
    "                if gnew==g:\n",
    "                    g2[g]=(g1[g][0]+num,g1[g][1]+1)\n",
    "                    if g2[g][1]>=k and ans<g2[g][0]*g:\n",
    "                        ans=g2[g][0]*g\n",
    "                else:\n",
    "                    if not (gnew in g2 and g2[gnew][0]>num+g1[g][0]):\n",
    "                        g2[gnew]=(num+g1[g][0],g1[g][1]+1)\n",
    "                        if g2[gnew][1]>=k and ans<g2[gnew][0]*gnew:\n",
    "                            ans=g2[gnew][0]*gnew\n",
    "                    \n",
    "            g1 = g2\n",
    "            # print(num,g1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGcdSum(self, nums: List[int], k: int) -> int:\n",
    "        nlis, res, k = {}, 0, k - 1\n",
    "        for i in nums:\n",
    "            nlis, lis = {}, nlis\n",
    "            if i not in lis: lis[i] = [0,0]\n",
    "            for x, (y,z) in lis.items():\n",
    "                a = gcd(i,x)\n",
    "                if nlis.get(a,[0,0])[0] <= y: nlis[a] = [y+1, z+i]\n",
    "                if y >= k: res = max(res, (z+i)*a)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGcdSum(self, nums: List[int], k: int) -> int:\n",
    "        res, cur = 0, [[0, 0, 0]] # [gcd, sum, len]\n",
    "        for x in nums:\n",
    "            nxt = []\n",
    "            for gd, sm, ln in cur:\n",
    "                gd = gcd(gd, x)\n",
    "                if not nxt or nxt[-1][0] != gd:\n",
    "                    nxt.append([gd, sm, ln])\n",
    "            if not nxt or nxt[-1][0] != x:\n",
    "                nxt.append([x, 0, 0])\n",
    "            for i in range(len(nxt)):\n",
    "                nxt[i][1] += x; nxt[i][2] += 1\n",
    "                if nxt[i][2] >= k and res < nxt[i][0] * nxt[i][1]:\n",
    "                    res = nxt[i][0] * nxt[i][1]\n",
    "                \n",
    "\n",
    "            cur = nxt\n",
    "            # print(cur)\n",
    "\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGcdSum(self, nums: List[int], k: int) -> int:\n",
    "        lis = {}\n",
    "        res = 0\n",
    "        k -= 1\n",
    "        for i in nums:\n",
    "            if i not in lis: lis[i] = [0,0]\n",
    "            nlis = {}\n",
    "            for x, (y,z) in lis.items():\n",
    "                a = gcd(i,x)\n",
    "                if nlis.get(a,[0,0])[0] <= y:\n",
    "                    nlis[a] = [y+1, z+i]\n",
    "                    if y >= k: res = max(res, (z+i)*a)\n",
    "            lis = nlis\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGcdSum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        ans = max(nums)**2 if k==1 else 0 #后面的代码对单个元素并没有更新答案，因此这里预处理这种情况\n",
    "        g1 = {} # g1表示旧的gcd记录，g2表示新的gcd记录\n",
    "\n",
    "        for num in nums:\n",
    "            g2 = {num:(num,1)} # 注意1个元素当然也算子数组，不能漏掉\n",
    "            for g in g1:\n",
    "                gnew = math.gcd(g,num)\n",
    "                if not (gnew in g2 and g2[gnew][0]>num+g1[g][0]): # 更新每个gcd的最大子数组和与最长子数组长度\n",
    "                    g2[gnew]=(num+g1[g][0],g1[g][1]+1)    \n",
    "                if g2[gnew][1]>=k and g2[gnew][0]*gnew>ans: # 更新答案，注意需要满足元素数量要求\n",
    "                    ans = g2[gnew][0]*gnew\n",
    "            g1 = g2\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGcdSum(self, nums: List[int], k: int) -> int:\n",
    "        nlis, res, k = {}, 0, k - 1\n",
    "        for i in nums:\n",
    "            nlis, lis = {}, nlis\n",
    "            if i not in lis: lis[i] = [0,0]\n",
    "            for x, (y,z) in lis.items():\n",
    "                a = gcd(i,x)\n",
    "                if nlis.get(a,[0,0])[0] <= y: nlis[a] = [y+1, z+i]\n",
    "                if y >= k: res = max(res, (z+i)*a)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGcdSum(self, nums: List[int], k: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        f = []\n",
    "        ans = 0\n",
    "        for i, v in enumerate(nums):\n",
    "            g = []\n",
    "            for j, x in f:\n",
    "                y = gcd(x, v)\n",
    "                if not g or g[-1][1] != y:\n",
    "                    g.append((j, y))\n",
    "            f = g\n",
    "            f.append((i, v))\n",
    "            for j, x in f:\n",
    "                if i - j + 1 >= k:\n",
    "                    ans = max(ans, (s[i + 1] - s[j]) * x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxGcdSum(self, nums: List[int], k: int) -> int:\n",
    "        ps = list(accumulate(nums, initial=0))\n",
    "        f = []\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            g = [(i, x)]\n",
    "            for j, y in f:\n",
    "                if y % x:\n",
    "                    x = gcd(y, x)\n",
    "                    g.append((j, x))\n",
    "            f = g\n",
    "            for (_, x), (j, y) in pairwise(f + [(-1, 0)]):\n",
    "                if i - j >= k:\n",
    "                    ans = max(ans, x * (ps[i + 1] - ps[j + 1]))\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
